#include "symtab.h"
#include "operator.h"
#include "parse.h"
#include "map.h"
#include "globals.h"



/* We use a dumb, simple hash table to look up symbols.
 * The table size is a prime number, since modulo a prime
 * is itself a nice distributor of values. 97 should be
 * fine for up to several hundred symbols. Realistically,
 * a linear search of a table would probably be fast
 * enough for most situations BLACC is likely to
 * encounter.
 */

#define HASH_TABLE_SIZE     (97)

typedef struct  TList
    {
    TSymbol**   Symbols;
    int         NSymbols;
    }           TList;

/* buffer used by SymbolStr() */
static
char*    StrBuffer;

static
SYMBOLS HashTable[HASH_TABLE_SIZE];

/* PatternCmp() - implement patterns for, well, operator patterns.
 *
 * Returns the position of the given pattern within an operator pattern.
 * Returns -1 if no match. Pattern operators include:
 * '^'   - matches start of string.
 * '$'   - matches end of string.
 * '*'   - matches any number of any kind of character.
 */
static int Match(const char* Pattern, const char* OpStr);

int     PatternCmp(const char* Pattern, const char* OpStr)
    {
    int         Result  = -1;       /* assume failure */
    int         StartPos, Len;
    int         LeftAnchor=FALSE;
    const char* P = Pattern;

    Len = (int)strlen(OpStr);

    if(*P == '^')
        {
        LeftAnchor  = TRUE;
        ++P;
        }
    for(StartPos=0; StartPos < Len; ++StartPos)
        {
        if(Match(P, OpStr+StartPos))
            {
            Result  = StartPos;
            break;
            }
        if(LeftAnchor)
            break;
        }

//    DumpVerbose("PatternCmp('%s', '%s') = %d\n", Pattern, OpStr, Result);
    return Result;
    }

/* Match() - simple recursive pattern matcher that does the real work.
 */
static
int Match(const char* Pattern, const char* OpStr)
    {
    int         PatChar, OpChar;
    const char* Rover;

    for(;;)
        {
        PatChar = *Pattern;
        if(PatChar == '\0')     /* if we got to end, then success! */
            return TRUE;
        OpChar  = *OpStr;
        switch(PatChar)
            {
            case '*':
                assert(Pattern[1] != '*');
                assert(Pattern[1] != '?');
                for(Rover=OpStr; ; ++Rover)
                    {
                    if(Match(Pattern+1, Rover))
                        return TRUE;
                    if(*Rover == '\0')
                        break;
                    }
                return FALSE;
            case '$'    :
                assert(Pattern[1] == '\0');
                return OpChar == '\0';
            case '?'    :   /* should not encounter this here */
                assert(FALSE);
                break;
            default:
                if(PatChar != OpChar)
                    {
                    if(Pattern[0] && Pattern[1] == '?')
                        ++Pattern;
                    else
                        return FALSE;
                    }
                else if(PatChar == '\0')
                    return TRUE;
                else
                    ++Pattern, ++OpStr;
                if(*Pattern == '?')
                    ++Pattern;
            }
        }
    }


/*  Literals - strings associated with terminals.
  
    The user can use the %token directive to associate a literal
    string with the name of a terminal symbol, like so:

    %token TK_INCR '++'

    This feature is required to make use of the operator precedence
    features of BLACC, like so:

    %right  ++X

    The preceding statement declares that there is a unary prefix
    operator with right associativity, and that the name of that
    operator can be found by looking in the literal pool under
    '++'.

*/

typedef struct  TLiteral
    {
    TToken      Literal;
    TSymbol*    Terminal;
    }           TLiteral;

static
int         NLiterals;

static
TLiteral*   Literals;

static
TSymbol* StartSymbol;
TSymbol* EndSymbol;
TSymbol* EolSymbol;
TSymbol* MatchAnySymbol;
TSymbol* NoActionSymbol;
TSymbol* ReduceSymbol;

/* SymbolInit() - initialize symbol table.
 *
 * There are a few symbols we need predefined. This
 * function gets them into the symbol table.
 */
void    SymbolInit(void)
    {
    /* hack: EndSymbol defined first so it will get assigned value of 0 */
    EndSymbol       = SymbolNewTerm(EOFToken);
//    EolSymbol       = SymbolNewTerm(EOLToken);
    MatchAnySymbol  = SymbolNewTerm(MatchAnyToken);
    NoActionSymbol  = SymbolNewTerm(NoActionToken);
    ReduceSymbol    = SymbolNewTerm(ReduceToken);
    }

static
void    SymbolFree(TSymbol* Symbol)
    {
    TRule**     Rover;
    
    if(Symbol->InputTokens)
        SymbolListDestroy(Symbol->InputTokens);
    if(Symbol->First)
        SymbolListDestroy(Symbol->First);
    if(Symbol->Follow)
        SymbolListDestroy(Symbol->Follow);
    if(Symbol->EndsWith)
        SymbolListDestroy(Symbol->EndsWith);
    if(Symbol->LLTable)
        free(Symbol->LLTable);
#if 0
    if(Symbol->Name.Text && InputIsFake(Symbol->Name))
        {
printf("Fake Token: %p  '%s'\n", Symbol->Name.Text, SymbolStr(Symbol));
        free((void*)Symbol->Name.Text);
        }
#endif
    Rover   = Symbol->Rules;
    if(Rover)
        {
        while(*Rover)
            {
            RuleFree(*Rover);
            ++Rover;
            }
        free(Symbol->Rules);
        }

    mwUnmark(Symbol, __FILE__, __LINE__);
    free(Symbol);
    }
    
void    RuleFree(TRule* Rule)
    {
    SymbolListDestroy(Rule->Symbols);
    SymbolListDestroy(Rule->First);
    if(Rule->Tokens)
        free((void*)Rule->Tokens);
    free(Rule);
    }

/* SymbolFini() - shut down the symbol table.
 *
 * This exists merely to get a clean bill of health from
 * memwatch.
 */
void    SymbolFini(void)
    {
    int iHash, iSym;

    SymbolListDestroy(Globals.Terminals);
    SymbolListDestroy(Globals.NonTerms);
    if(StrBuffer)
        free(StrBuffer);
    for(iHash=0; iHash < HASH_TABLE_SIZE; ++iHash)
        {
        TSymbol*    Symbol;
        SYMBOLS     List = HashTable[iHash];

        if(List)
            {
            for(iSym=0; (Symbol=SymbolListGet(List, iSym)) != NULL; ++iSym)
                SymbolFree(Symbol);
            SymbolListDestroy(List);
            }
        }
    if(Literals)
        free(Literals);
    }


int SymbolIsEqual(TSymbol* A, TSymbol* B)
    {
    // ??? TODO: revise later
    return A == B;
    }


/*TSymbol*    StartSymbol; */

/* SymbolNewNonTerm() - create a new non-terminal data structure.
 *
 * We assume someone else has already verified that no symbol
 * with this name already exists.
 */
TSymbol*   SymbolNewNonTerm(TToken Token)
    {
    TSymbol*    Result;

    Result              = SymbolAdd(Token, !SYM_TERMINAL);
    Globals.NonTerms    = SymbolListAdd(Globals.NonTerms, Result);

    return Result;
    }

/* SymbolNewTerm() - create a new terminal data structure.
 *
 * We assume someone else has already verified that no symbol
 * with this name already exists.
 */
TSymbol*    SymbolNewTerm(TToken Token)
    {
    TSymbol*    Result;

    if(SymbolFind(Token))
        ErrorExit(ERROR_TERM_ALREADY_DEFINED, "Terminal already defined: '%.*s'\n",
              Token.TextLen, Token.Text);

    Result  = SymbolAdd(Token, SYM_TERMINAL);
    assert(Result != NULL);


    Globals.Terminals   = SymbolListAdd(Globals.Terminals, Result);

    /* Bit of a hack, but we'll set ->First here.
     * the FIRST() set of a terminal is just the terminal
     */
    Result->First   = SymbolListAdd(Result->First, Result);

    return Result;
    }


/* SymbolListContains() - does the symbol list already contain this symbol?
 *
 * If it does, we return the index plus 1, which is used elsewhere.
 */
int         SymbolListContains(SYMBOLS Handle, TSymbol* Symbol)
    {
    TList*  List    = (TList*)Handle;
    int     Result  = FALSE;

    if(List)
        {
        int     iList;

        for(iList = 0; iList < List->NSymbols; ++iList)
            if(List->Symbols[iList] == Symbol)
                {
                Result  = iList + 1;
                break;
                }
        }
        
    return Result;
    }

/* SymbolListAddFirst() - add FIRST list of symbol to existing list.
 *
 */
SYMBOLS SymbolListAddFirst(SYMBOLS List, TSymbol* ProdItem)
    {

    /* FIRST(X) is just X, if X is a terminal */
    if(SymbolGetBit(ProdItem, SYM_TERMINAL))
        List = SymbolListAddUnique(List, ProdItem);
    /* otherwise, we have to add one set of symbols to another */
    else if(ProdItem->First)
        SymbolListAddList(&List, ProdItem->First);

    return List;
    }

/* SymbolListCopy() - copy one list to another.
 *
 * It's OK if To is NULL, SymbolListCopy() will create and
 * return a new list. If both To and From are NULL, the function
 * returns NULL.
 */
SYMBOLS     SymbolListCopy(SYMBOLS To, SYMBOLS From)
    {
    int         iSymbol;
    TSymbol*    Symbol;

    if(To == NULL && SymbolListCount(From))
        To      = SymbolListCreate();
    SymbolListTruncate(To, 0);
    for(iSymbol=0; (Symbol=SymbolListGet(From, iSymbol)) != NULL; ++iSymbol)
        To      = SymbolListAdd(To, Symbol);
    return To;
    }

/* SymbolListAddUnique() - add symbol only if it's not already in list.
 */
SYMBOLS SymbolListAddUnique(SYMBOLS Handle, TSymbol* Symbol)
    {
    if(!SymbolListContains(Handle, Symbol))
        Handle  = SymbolListAdd(Handle, Symbol);

    return Handle;
    }

/* SymbolListRemove() - remove any/all occurrences of a given symbol.
 */
int SymbolListRemove(SYMBOLS Handle, TSymbol* Symbol)
    {
    int     RemoveCount = 0;
    int     iList;
    TList*  List;

    if(Handle != NULL)
        {
        List    = (TList*)Handle;
    
        for(iList = 0; iList < List->NSymbols; ++iList)
            {
            TSymbol*    This = List->Symbols[iList];
    
            if(This == Symbol)
                {
                int     iNext   = iList+1;
                
                if(iNext < List->NSymbols)
                    memmove(&List->Symbols[iList], &List->Symbols[iNext],
                        sizeof(TSymbol*)*(List->NSymbols - iNext));
                --List->NSymbols;
                --iList;
                }
            }
        }
    
    return RemoveCount;
    }

/* SymbolListReplace() - replace one symbol with a list of symbols.
 */
SYMBOLS     SymbolListReplace(SYMBOLS List, int Pos, SYMBOLS Insert)
    {
    int         iSymbol, nSymbols;
    SYMBOLS     New = NULL;

    nSymbols    = SymbolListCount(List);
    for(iSymbol=0; iSymbol < Pos && iSymbol < nSymbols; ++iSymbol)
        New     = SymbolListAdd(New, SymbolListGet(List, iSymbol));
    nSymbols    = SymbolListCount(Insert);
    for(iSymbol=0; iSymbol < nSymbols; ++iSymbol)
        New     = SymbolListAdd(New, SymbolListGet(Insert, iSymbol));
    nSymbols    = SymbolListCount(List);
    for(iSymbol=Pos+1; iSymbol < nSymbols; ++iSymbol)
        New     = SymbolListAdd(New, SymbolListGet(List, iSymbol));

    List    = SymbolListCopy(List, New);
    SymbolListDestroy(New);

    return List;
    }


/* SymbolStr() - return a null-terminated string for the symbol name.
 *
 * I should, of course, burn in hell for this, but I got tired of the
 * tedious and never-ending coding of this form:
 *     printf("'%.*s'\n", NonTerm->Name.TextLen, NonTerm->Name.Text);
 * This function is technically "unsafe" because the returned strings
 * are eventually overwritten. Just don't use it except to obtain
 * a temporary result for printf()-style functions and it'll do fine.
 */
const char* SymbolStr(TSymbol* Symbol)
    {
    static char*    Rover;
    static char*    Sentinel;
    char*           Result;
    int             Len;

    if(StrBuffer == NULL)
        {
        StrBuffer      = malloc(1024*8);
        assert(StrBuffer != NULL);
        Rover       = StrBuffer;
        Sentinel    = StrBuffer + 1024*8;
        }
    if(Symbol)
        Len     = Symbol->Name.TextLen + 1;
    else
        Len     = strlen("(NULL)") + 1;
    if(Rover + Len >= Sentinel)
        Rover   = StrBuffer;
    assert(Rover + Len < Sentinel);
    if(Symbol)
        sprintf(Rover, "%.*s", Symbol->Name.TextLen, Symbol->Name.Text);
    else
        strcpy(Rover, "(NULL)");

    Result  = Rover;
    Rover  += Len;

    return Result;
    }

TSymbol* SymbolListDelete(SYMBOLS Handle, int Position)
    {
    TSymbol*    Result;
    int         Next;
    TList*      List;

    assert(Handle != NULL);
    List    = (TList*)Handle;
    assert(Position >= 0);
    assert(Position < List->NSymbols);

    Result  = List->Symbols[Position];
    Next    = Position+1;
                
    if(Next < List->NSymbols)
        memmove(&List->Symbols[Position], &List->Symbols[Next],
            sizeof(TSymbol*)*(List->NSymbols - Next));
    --List->NSymbols;
    
    return Result;
    }

SYMBOLS SymbolListTruncate(SYMBOLS List, int NewLen)
    {
    while(SymbolListCount(List) > NewLen)
        SymbolListDelete(List, NewLen);
    return List;
    }


/* SymbolListIntersect() - return the intersection of two TSymbol* lists.
 *
 * Only tricky part is that either list could be NULL.
 */
SYMBOLS SymbolListIntersect(SYMBOLS A, SYMBOLS B)
    {
    int         iSym;
    TSymbol*    Symbol;
    SYMBOLS     Result  = NULL;

    if(A && B)
        for(iSym = 0; iSym < SymbolListCount(A); ++iSym)
            {
            Symbol  = SymbolListGet(A, iSym);
            if(SymbolListContains(B, Symbol))
               Result   = SymbolListAddUnique(Result, Symbol);
            }
    return Result;
    }


/* SymbolListAddList() - add second list to first.
 *
 * In this case, the "lists" are really sets. We only
 * add symbols from the second set that are not already in
 * the first set. The return value is true if any new symbols
 * were added.
 */
int         SymbolListAddList(SYMBOLS* List, SYMBOLS Add)
    {
    int         Result  = FALSE;
    SymIt       Symbols = SymItNew(Add);

    while(SymbolIterate(&Symbols))
        if(!SymbolListContains(*List, Symbols.Symbol))
            {
            *List   = SymbolListAdd(*List, Symbols.Symbol);
            Result  = TRUE;
            }
    return Result;
    }

/* SymbolListEqual() - are two lists equivalent?
 *
 * This is just a simple, sequential compare.
 */
int         SymbolListEqual(SYMBOLS A, SYMBOLS B)
    {
    int     Result = FALSE;         /* assume they won't be equal */
    int     ACount, BCount;
    int     iSymbol;

    ACount  = SymbolListCount(A);
    BCount  = SymbolListCount(B);
    if(ACount == BCount)
        {
        for(iSymbol = 0; iSymbol < ACount; ++iSymbol)
            if(SymbolListGet(A, iSymbol) != SymbolListGet(B, iSymbol))
                break;
        if(iSymbol >= ACount)
            Result  = TRUE;
        }

    return Result;
    }


/* SymbolListGet() - get an symbol from a SYMBOLS list.
 *
 * It is benign to give us an invalid index; we merely
 * return NULL.
 */
TSymbol*    SymbolListGet(SYMBOLS Handle, int Index)
    {
    TSymbol*    Result  = NULL;
    TList*      List;

    List    = (TList*)Handle;

    if(List)
        {
        if(Index >= 0 && Index < List->NSymbols)
            Result  = List->Symbols[Index];
        }

    return Result;
    }

TSymbol*    SymbolListFind(SYMBOLS Handle, TToken Token)
    {
    TSymbol*    Result  = NULL;
    TList*      List;
    int         iSymbol;

    List    = (TList*)Handle;

    if(List)
        for(iSymbol = 0; iSymbol < List->NSymbols; ++iSymbol)
            if(TokenEqual(Token, List->Symbols[iSymbol]->Name))
                {
                Result  = List->Symbols[iSymbol];
                break;
                }

    return Result;
    }

/* SymbolListDumpStr() - print list of symbols into string.
 *
 * Useful both in debugging output, and for creating nice comments
 * in generated code.
 */
char*       SymbolListDumpStr(SYMBOLS List, const char* Sep)
    {
    char*       Buffer;
    char*       Rover;
    int         iSymbol, NSymbols = 0;

    Buffer      = malloc(1000);
    Buffer[0]   = '\0';
    Rover       = Buffer;
    if(List)
        {
        TSymbol*    Symbol;

        NSymbols    = SymbolListCount(List);
        for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
            {
            Symbol  = SymbolListGet(List, iSymbol);

            sprintf(Rover, "%s", iSymbol ? Sep : "");
            Rover += strlen(Rover);
            if(Symbol == NULL)
                sprintf(Rover, "X");
            else if(SymbolIsAction(Symbol))
                sprintf(Rover, "{}");
            else
                sprintf(Rover, "%.*s",
                    Symbol->Name.TextLen, Symbol->Name.Text);
            }
        }

    return Buffer;
    }

#if 0
int         SymbolListDumpf(FILE* Handle, const char* Format, SYMBOLS List, ...)
    {
    int         iSymbol, NSymbols = 0;

    if(List)
        {
        TSymbol*    Symbol;

        NSymbols    = SymbolListCount(List);
        for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
            {
            Symbol  = SymbolListGet(List, iSymbol);

            fprintf(Handle, "%s", iSymbol ? Sep : "");
            if(Symbol == NULL)
                fprintf(Handle, "X");
            else if(SymbolIsAction(Symbol))
                fprintf(Handle, "{}");
            else
                fprintf(Handle, "%.*s",
                    Symbol->Name.TextLen, Symbol->Name.Text);
            }
        }

    return NSymbols;

    }
#endif

/* SymbolListDump() - print out a list of symbols.
 *
 * Useful both in debugging output, and for creating nice comments
 * in generated code.
 */
int    SymbolListDump(FILE* Handle, SYMBOLS List, const char* Sep)
    {
    int iSymbol, NSymbols   = 0;
    int And                 = FALSE;
    int NoActions           = FALSE;
    int Last;

    if(List)
        {
        TSymbol*    Symbol;

        if(*Sep == '{')
            {
            NoActions   = TRUE;
            ++Sep;
            }
        /* if special separator */
        if(!strcmp(Sep, ",and"))
            {
            And     = TRUE;
            Sep     = ", ";
            }
        NSymbols    = SymbolListCount(List);
        /* locate last (printing) symbol */
        if(NoActions)
            {
            Last    = -1;
            for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
                if(!SymbolIsAction(SymbolListGet(List, iSymbol)))
                    Last    = iSymbol;
            }
        else
            Last    = NSymbols-1;
        for(iSymbol = 0; iSymbol < NSymbols; ++iSymbol)
            {
            const char* Text;
            const char* ThisSep = Sep;

            Symbol  = SymbolListGet(List, iSymbol);

            if(NoActions && SymbolIsAction(Symbol))
                continue;
            if(iSymbol == 0)
                ThisSep = "";
            else if(And && iSymbol == Last)
                ThisSep = ", and ";
            fputs(ThisSep, Handle);

            if(Symbol == NULL)
                Text    = "X";
            else
                Text    = SymbolStr(Symbol);
            fputs(Text, Handle);
            }
        }

    return NSymbols;
    }



int         SymbolListIndex(SYMBOLS Handle, TSymbol* Symbol)
    {
    int         Result  = -1;
    TList*      List;
    int         iSymbol;

    List    = (TList*)Handle;

    if(List)
        for(iSymbol = 0; iSymbol < List->NSymbols; ++iSymbol)
            if(Symbol == List->Symbols[iSymbol])
                {
                Result  = iSymbol;
                break;
                }

    return Result;
    }

int         SymbolListCount(SYMBOLS Handle)
    {
    TList*      List;

    List    = (TList*)Handle;

    return List ? List->NSymbols : 0;
    }

/* SymbolListCountSig() - count "significant" (non-actions) in list.
 */
int         SymbolListCountSig(SYMBOLS Handle)
    {
    TList*  List    = (TList*)Handle;
    int     Result  = 0;

    if(List)
        {
        int     iList;

        for(iList = 0; iList < List->NSymbols; ++iList)
            if(!SymbolIsAction(List->Symbols[iList]))
                ++Result;
        }
        
    return Result;
    }

/* SymbolListTop() - return symbol on top of stack.
 */
TSymbol*    SymbolListTop(SYMBOLS Handle)
    {
    TList*      List;
    TSymbol*    Result  = NULL;

    assert(Handle != NULL);

    List    = (TList*)Handle;
    if(List->NSymbols)
        {
        List->NSymbols;
        Result  = List->Symbols[List->NSymbols-1];
        }

    return Result;
    }


TSymbol*    SymbolListPop(SYMBOLS Handle)
    {
    TList*      List;
    TSymbol*    Result  = NULL;

    assert(Handle != NULL);

    List    = (TList*)Handle;
    if(List->NSymbols)
        {
        --List->NSymbols;
        Result  = List->Symbols[List->NSymbols];
        }

    return Result;
    }

static
MAP         MapIdToSymbol;

static
int CompareSymId(void* A, size_t ALen, void* B, size_t BLen)
    {
    assert(ALen == 0 && BLen == 0);
    return (int)A != (int)B;
    }


TSymbol*    SymbolFromValue(int Value)
    {
    TSymbol*    Result = NULL;

    if(MapIdToSymbol)
        Result      = (TSymbol*)MapFind(MapIdToSymbol, (void*)Value, 0);

printf("SymbolFromValue(%d)='%s'\n", Value,
       Result ? SymbolStr(Result) : "");
    return Result;
    }

TSymbol*    SymbolSetValue(TSymbol* Symbol, int Value)
    {
    TSymbol*    Result = Symbol;

    if(MapIdToSymbol == NULL)
        {
        MapIdToSymbol   = MapCreate(CompareSymId);
        assert(MapIdToSymbol != NULL);
        }
    Result  = (TSymbol*)MapAdd(MapIdToSymbol, (void*)Value, 0, (void*)Symbol);
    assert(Result == Symbol);
    Symbol->Value   = Value;

    return Result;
    }


SymIt       SymItNew(SYMBOLS List)
    {
    SymIt   Result = {NULL, NULL, -1, -1};

    Result.List     = List;
    Result.Count    = SymbolListCount(List);
    
    return Result;
    }

int         SymbolIterate(SymIt* Info)
    {
    int     Result  = FALSE;

    Info->Count = SymbolListCount(Info->List);
    if(++Info->Index < Info->Count)
        {
        Result          = TRUE;
        Info->Symbol    = SymbolListGet(Info->List, Info->Index);
        }
    return Result;
    }


RuleIt  RuleItNew(TSymbol* Root)
    {
    RuleIt  Result = {0};

    Result.Root     = Root;
    Result.NRules   = RuleCount(Root);
    Result.iRule    = -1;

    return Result;
    }

/* RuleIterate() - iterate across a symbol's rules.
 *
 * The start condition is that all the indices are 0 except for
 * iRule, which is -1. That makes iProdItem equal to NProdItems (both 0),
 * which causes an immediate advance to the next rule by incrementing
 * iRule, which sets it to 0.
 */
int     RuleIterate(RuleIt* Info)
    {
    int     Result  = FALSE;

    if(!Info->Finished)    /* don't even start if this iteration already completed */
        {
        ++Info->iProdItem;        /* advance to new symbol */
        /* while current rule is exhausted */
        while(Info->iProdItem > Info->NProdItems - 1)
            {
            if(++Info->iRule >= Info->NRules)
                break;
            Info->Rule      = Info->Root->Rules[Info->iRule];
            Info->iProdItem = 0;
            Info->NProdItems= SymbolListCount(Info->Rule->Symbols);
            }
        /* if iteration not completed yet */
        if(Info->iRule < Info->NRules)
            {
            Result  = TRUE;
            Info->ProdItem    = SymbolListGet(Info->Rule->Symbols, Info->iProdItem);
            }
        }
    Info->Finished = (Result == FALSE);

    return Result;
    }

/* RuleItNext() - advance to next rule in interation.
 */
void    RuleItNext(RuleIt* Info)
    {
    Info->iProdItem = Info->NProdItems;
    }


/* RuleCount() - count the # of rules a symbol has.
 *
 * It's a null-terminated array of pointers.
 */
int     RuleCount(TSymbol* Symbol)
    {
    int     Result = 0;
    TRule** RulePtr;

    RulePtr     = Symbol->Rules;
    if(RulePtr)
        while(*RulePtr++)
            ++Result;

    return Result;
    }


#if 0
int  RuleCmp(TSymbol* NonTerm, SYMBOLS AList, SYMBOLS BList)
    {
    int         iA, nA, iB, nB;
    TSymbol*    A;
    TSymbol*    B;
    SYMBOLS     Common = NULL;
    int         MatchCount;
    int         ActionCount, FoundActions, LastSymbolMatched;


printf(".   RuleCmp('%s') comparing rules:\n.     -> ", SymbolStr(NonTerm));
        SymbolListDump(stdout, AList, " ");
        printf("\n.     -> ");
        SymbolListDump(stdout, BList, " ");
        printf("\n");

    nA          = SymbolListCount(AList);
    nB          = SymbolListCount(BList);

    ActionCount         = 0;
    FoundActions        = FALSE;
    LastSymbolMatched   = FALSE;
    A   = B     = NULL;
    for(iA=iB=0; iA < nA || iB < nB; ++iA,++iB)
        {
        /* advance to next "real" symbol in AList (if any) */
        for(A = NULL; iA < nA; ++iA)
            {
            A   = SymbolListGet(AList, iA);
            if(SymbolIsAction(A))
                {
                A   = NULL;
                ++ActionCount;
                }
            else
                break;
            }
        /* advance to next "real" symbol in BList (if any) */
        for(B = NULL; iB < nB; ++iB)
            {
            B   = SymbolListGet(BList, iB);
            if(SymbolIsAction(B))
                {
                B   = NULL;
                ++ActionCount;
                }
            else
                break;
            }
        /* if there was another symbol in both productions */
        if(A != NULL || B != NULL)
            {
            /* If both productions share another prefix symbol */
            if(A == B)
                {
                LastSymbolMatched   = TRUE;
                if(ActionCount)
                    FoundActions    = TRUE;
                Common  = SymbolListAdd(Common, A);
                continue;
                }
            else
                {
                LastSymbolMatched   = FALSE;
                break;
                }
            }
        /* else, we must have exhausted both lists */
        assert(iA >= nA && iB >= nB);
        }
    MatchCount  = SymbolListCount(Common);

    if(LastSymbolMatched == TRUE)
        {
        fprintf(stderr, "Nonterminal '%s' has two or more rules with identical symbols:\n", SymbolStr(NonTerm));
        SymbolListDump(stderr, Common, " ");
        fprintf(stderr, "\n");
        Exit(-1, ERROR_RULES_ARE_IDENTICAL);
        }
    /* */
    else if(MatchCount > 0)
        {
        fprintf(stdout, "    # of common left symbols=%d: ", SymbolListCount(Common));
        SymbolListDump(stdout, Common, " ");
        printf("\n");
        if(FoundActions)
            {
            fprintf(stderr, "Nonterminal '%s': %s\n",
                    SymbolStr(NonTerm),
                    "two rules share a common prefix containing embedded actions\n");
            fprintf(stderr, "  -> ");
            SymbolListDump(stderr, AList, " ");
            fprintf(stderr, "\n");
            fprintf(stderr, "  -> ");
            SymbolListDump(stderr, BList, " ");
            fprintf(stderr, "\n");

            Exit(-1, ERROR_COMMON_PREFIX_CONTAINS_ACTION);
            }
        }
    SymbolListDestroy(Common);
fprintf(stderr, "    LastSymbolMatched=%d, MatchCount=%d\n", LastSymbolMatched, MatchCount);

    return MatchCount;
    }

#endif

/* RuleItemCount() - return count of items, minus any trailing actions.
 *
 */
int     RuleItemCount(TRule* Rule)
    {
    int     NSymbols;
    SYMBOLS ProdItems   = Rule->Symbols;

    NSymbols    = SymbolListCount(ProdItems);
    if(NSymbols > 0 && SymbolIsAction(SymbolListGet(ProdItems, NSymbols-1)))
        --NSymbols;

    return NSymbols;
    }

/* RuleFirst() - return FIRST set for suffix of production.
 *
 * Note that it is benign if iProdItem refers past the last
 * production item; the result is simply an empty set.
 *
 * Note also that we must produce a correct result even if
 * the rule contains direct left recursion. Suppose the rule
 * looks like this:
 *     X -> X s1 s2 ... sn
 * 
 */
SYMBOLS RuleFirst(TSymbol* NonTerm, TRule* Rule, int iProdItem)
    {
    int         DLR         = FALSE;    /* assume rule is not direct left recursion */
    TSymbol*    Symbol;
    SYMBOLS     First       = NULL;
    int         NProdItems  = SymbolListCount(Rule->Symbols);

    NProdItems = SymbolListCount(Rule->Symbols);
    if(NProdItems > 0)
        if(SymbolIsAction(SymbolListGet(Rule->Symbols, NProdItems-1)))
            --NProdItems;
    if(SymbolListGet(Rule->Symbols, 0) == NonTerm)
        DLR     = TRUE;

    for(; iProdItem < NProdItems; ++iProdItem)
        {
        Symbol  = SymbolListGet(Rule->Symbols, iProdItem);
        SymbolListAddList(&First, Symbol->First);
        if(!Symbol->Nullable)
            break;
        }
#if 0
    if(DLR && iProdItem >= NProdItems)
        {
        for(iProdItem=1; iProdItem < NProdItems; ++iProdItem)
            {
            Symbol  = SymbolListGet(Rule->Symbols, iProdItem);
            SymbolListAddList(&First, Symbol->First);
            if(!Symbol->Nullable)
                break;
            }
        }
#endif
    return First;
    }

/* RuleNullable() - is a suffix of a production nullable?
 *
 * If the caller set iProdItem past the end of the production
 * list, then we claim "TRUE".
 */
int     RuleNullable(TRule* Rule, int Position)
    {
    int         NProdItems, iProdItem;
    int         Nullable = TRUE;
    TSymbol*    Symbol;

    NProdItems  = SymbolListCount(Rule->Symbols);
    if(Position < NProdItems)
        {
        iProdItem   = Position;
        while((Symbol=SymbolListGet(Rule->Symbols, iProdItem)) != NULL && Symbol->Nullable)
            ++iProdItem;

        if(iProdItem < NProdItems)
            Nullable    = FALSE;
        }
    if(Globals.Dump && Globals.Verbose > 1)
        {
        fprintf(stderr, "RuleNullable([%d]-> ", Position);
        SymbolListDump(stderr, Rule->Symbols, " ");
        fprintf(stderr, ") = %d\n", Nullable);
        }
    return Nullable;
    }

/* RuleIsNull() - is this rule an epsilon production?
 *
 * Note that this is a test of whether the rule is empty
 * or not, not a question of nullability.
 *
 */
int     RuleIsNull(TRule* Rule)
    {
    return Rule->Symbols == NULL || SymbolListCount(Rule->Symbols) == 0;
    }



static
size_t  Hash(const char* Name, size_t Len)
    {
    size_t  Result  = Len;

    while(Len-- > 0)
        Result  = (Result << 5) ^ *Name++;

    return Result % HASH_TABLE_SIZE;
    }


TSymbol*    SymbolFind(TToken Token)
    {
    TSymbol*    Result      = NULL;
    size_t      Index;
    SYMBOLS     Symbols;

    Index           = Hash(Token.Text, Token.TextLen);
    Symbols         = HashTable[Index];
    if(Symbols != NULL)
        Result      = SymbolListFind(Symbols, Token);

    return Result;
    }

/* SymbolAdd() - add a new symbol to the global symbol table.
 *
 * This is the sole location where a new TSymbol structure is
 * allocated.
 */
TSymbol*    SymbolAdd(TToken Token, int Type)
    {
    TSymbol*    Symbol;
    size_t      Index;

    assert(Type == SYM_TERMINAL || Type == 0);

    Index           = Hash(Token.Text, Token.TextLen);

    /* assert that no one has added this symbol before */
    if(HashTable[Index])
        {
        SymIt       Symbols = SymItNew(HashTable[Index]);

        while(SymbolIterate(&Symbols))
            if(Symbols.Symbol->Name.TextLen == Token.TextLen)
                assert(strncmp(Symbols.Symbol->Name.Text, Token.Text, Token.TextLen));
        }

    Symbol          = NEW(TSymbol);
    assert(Symbol != NULL);
    mwMark(Symbol, "NEW(TSymbol)", __FILE__, __LINE__);

    Symbol->Name        = Token;
    if(Type)
        SymbolSetBit(Symbol, Type);

    HashTable[Index]    = SymbolListAdd(HashTable[Index], Symbol);

    return Symbol;
    }

/* SymbolIsAction() - is this symbol just a dummy for an action?
 *
 * We create a dummy non-terminal for every action. This function
 * returns TRUE if that's what kind of symbol this is.
 */
int SymbolIsAction(TSymbol* Symbol)
    {
    return Symbol->Action != NULL;
    }

/* SymbolIsEmpty() - does this symbol derive anything at all?
 *
 * Returns TRUE if this symbol produces absolutely nothing. Since
 * actions are stored as empty non-terminals, there will be a fair
 * number of empty non-terminals even if the user declared none
 * explicitly.
 *
 * Often, we need to treat actions differently from other non-terminals,
 * but sometimes we can lump actions in with any other non-terminal that
 * is empty (as in when searching for left recursion).
 */
int         SymbolIsEmpty(TSymbol* Symbol)
    {
    return (Symbol->Bits & SYM_EMPTY) != 0;
    }


int         SymbolIsTerminal(TSymbol* Symbol)
    {
    return (Symbol->Bits & SYM_TERMINAL) != 0;
    }

int         SymbolIsNullable(TSymbol* A)
    {
    return A->Nullable;
    }


int         SymbolIsOpSyms(TSymbol* Symbol)
    {
    TRule**     Rover;
//    int         iRule, NRules;
    TRule*      Rule;
    TSymbol*    OpSym;

    Rover   = Symbol->Rules;
    if(Rover)
        {
        for(; *Rover; ++Rover)
            {
            Rule    = *Rover;

            if(SymbolListCount(Rule->Symbols) != 1)
                return FALSE;
            OpSym   = SymbolListGet(Rule->Symbols, 0);
            if(!OperatorFindOpSym(NULL, OpSym))
                return FALSE;
            }
        }

    return TRUE;
    }

SYMBOLS SymbolGetAllSymbols(TSymbol* Symbol)
    {
    TRule**     Rover;
    TRule*      Rule;
    SYMBOLS     List    = NULL;

    Rover   = Symbol->Rules;
    if(Rover)
        for(; *Rover; ++Rover)
            {
            Rule    = *Rover;
            SymbolListAddList(&List, Rule->Symbols);
            }

    return List;
    }

/* SymbolStart() - return the implicit start symbol.
 *
 */
TSymbol*    SymbolStart(void)
    {
    return StartSymbol;
    }
    
/* SymbolAddStart() - add a new start symbol.
 *
 * Adding a start symbol consists of adding a new right-hand-side
 * to the implicit start symbol that consists of the given symbol
 * followed by the end symbol.
 */
TSymbol*    SymbolAddStart(TSymbol* NewStart)
    {
    TRule*  NewRule;
    
    if(StartSymbol == NULL)
        StartSymbol     = SymbolNewNonTerm(StartToken);
    assert(StartSymbol != NULL);

    NewRule             = SymbolNewRule(StartSymbol);
    assert(NewStart != NULL);
    NewRule->Symbols    = SymbolListAdd(NewRule->Symbols, NewStart);
    assert(EndSymbol != NULL);
    NewRule->Symbols    = SymbolListAdd(NewRule->Symbols, EndSymbol);

    return StartSymbol;
    }


int         SymbolSetBit(TSymbol* Symbol, int Bit)
    {
    int     Result = Symbol->Bits & ~Bit;

    Symbol->Bits   |= Bit;
    return Result;
    }
int         SymbolGetBit(TSymbol* Symbol, int Bit)
    {
    return Symbol->Bits & Bit;
    }   


/* SymbolDupRule() - add a copy of a rule to an existing non-terminal
 */
TRule*      SymbolDupRule(TSymbol* Symbol, TRule* OldRule)
    {
    int     NewCount    = RuleCount(Symbol) + 1;
    TRule*  NewRule     = NEW(TRule);

    assert(NewRule != NULL);
    assert(Symbol != NULL);
    assert(SymbolGetBit(Symbol, SYM_TERMINAL) == FALSE);

    NewRule->Nullable   = OldRule->Nullable;
    NewRule->Predicate  = OldRule->Predicate;
    NewRule->Symbols    = SymbolListCopy(NULL, OldRule->Symbols);
    NewRule->First      = SymbolListCopy(NULL, OldRule->First);


    Symbol->Rules  = (TRule**)realloc(Symbol->Rules, (NewCount+1)*sizeof(TRule*));
    assert(Symbol->Rules != NULL);
    Symbol->Rules[NewCount-1]   = NewRule;
    Symbol->Rules[NewCount]     = NULL;         /* null-terminate array of pointers */

    return NewRule;
    }

TRule*  RuleDup(TRule* OldRule)
    {
    TRule*  NewRule     = NEW(TRule);

    assert(NewRule != NULL);

    NewRule->Nullable   = OldRule->Nullable;
    NewRule->Predicate  = OldRule->Predicate;
    NewRule->Symbols    = SymbolListCopy(NULL, OldRule->Symbols);

    return NewRule;
    }


/* SymbolNewRule() - add a rule to an existing non-terminal
 */
TRule*      SymbolNewRule(TSymbol* Symbol)
    {
    int     NewCount    = RuleCount(Symbol) + 1;
    TRule*  NewRule     = NEW(TRule);

    assert(NewRule != NULL);
    assert(Symbol != NULL);
    assert(SymbolGetBit(Symbol, SYM_TERMINAL) == FALSE);

    Symbol->Rules  = (TRule**)realloc(Symbol->Rules, (NewCount+1)*sizeof(TRule*));
    assert(Symbol->Rules != NULL);
    Symbol->Rules[NewCount-1]   = NewRule;
    Symbol->Rules[NewCount]     = NULL;         /* null-terminate array of pointers */

    return NewRule;
    }

TRule*      SymbolAddRule(TSymbol* Symbol, TRule* NewRule)
    {
    int     NewCount    = RuleCount(Symbol) + 1;

    assert(NewRule != NULL);
    assert(Symbol != NULL);
    assert(SymbolGetBit(Symbol, SYM_TERMINAL) == FALSE);

    Symbol->Rules  = (TRule**)realloc(Symbol->Rules, (NewCount+1)*sizeof(TRule*));
    assert(Symbol->Rules != NULL);
    Symbol->Rules[NewCount-1]   = NewRule;
    Symbol->Rules[NewCount]     = NULL;         /* null-terminate array of pointers */

    return NewRule;
    }

TToken      Unquote(TToken Token)
    {
    if(Token.TextLen > 2 && Token.Text[0] == '\'' && Token.Text[Token.TextLen-1] == '\'')
        {
        ++Token.Text;
        Token.TextLen   -= 2;
        }
    return Token;
    }

TSymbol*    LiteralFind(TToken Token)
    {
    TSymbol*    Result      = NULL;
    int         iLiteral;

    Token   = Unquote(Token);
    for(iLiteral = 0; iLiteral < NLiterals; ++iLiteral)
        if(TokenEqual(Token, Literals[iLiteral].Literal))
            {
            Result      = Literals[iLiteral].Terminal;
            break;
            }
    return Result;
    }

TToken  LiteralFromSymbol(TSymbol* Symbol)
    {
    TToken      Result      = { 0 };
    int         iLiteral;

    for(iLiteral = 0; iLiteral < NLiterals; ++iLiteral)
        if(Literals[iLiteral].Terminal == Symbol)
            {
            Result      = Literals[iLiteral].Literal;
            break;
            }
    return Result;
    }

/* LiteralAdd() - associate a literal with a symbol.
 *
 * We assume the caller will use LiteralFind() to avoid adding
 * the same literal twice, or associating the same literal with
 * more than one symbol.
 */
void        LiteralAdd(TSymbol* Symbol, TToken Token)
    {
    ++NLiterals;
    Literals    = realloc(Literals, sizeof(TLiteral)*NLiterals);
    assert(Literals != NULL);

    Token   = Unquote(Token);
    Literals[NLiterals-1].Terminal  = Symbol;
    Literals[NLiterals-1].Literal   = Token;
    }

/*******************
 * Rule functions  *
 *******************/

void        RuleAddSymbol(TRule* Rule, TSymbol* Symbol, TToken Token)
    {
    int     NSymbols;
    
    Rule->Symbols       = SymbolListAdd(Rule->Symbols, Symbol);
    NSymbols            = SymbolListCount(Rule->Symbols);
    Rule->Tokens        = (TToken *)realloc((void*)Rule->Tokens, sizeof(TToken)*NSymbols);
    Rule->Tokens[NSymbols-1]   = Token;
    }

TSymbol*    RuleRemoveSymbol(TRule* Rule, int Pos)
    {
    int         NSymbols, iToken;
    TSymbol*    Result = NULL;
    SYMBOLS     Symbols;

    Symbols     = Rule->Symbols;
    NSymbols    = SymbolListCount(Symbols);

    if(Pos < NSymbols)
        {
        Result  = SymbolListDelete(Symbols, Pos);
        /* might be no tokens if, for example, rule was victim of
         * a left-corner transformation.
         */
        if(Rule->Tokens)
            for(iToken = Pos; iToken < NSymbols-1; ++iToken)
                Rule->Tokens[iToken] = Rule->Tokens[iToken+1];
        }

    return Result;
    }


/* these come last, so I can safely undef their macro
 * aliases.
 */

#undef SymbolListCreate
SYMBOLS     SymbolListCreate(void)
    {
    return (SYMBOLS)NEW(TList);
    }

#undef SymbolListDestroy
SYMBOLS     SymbolListDestroy(SYMBOLS Handle)
    {
    TList*  List    = (TList*)Handle;

    if(List)
        {
        if(List->Symbols)
            free(List->Symbols);
        free(List);
        }

    return NULL;
    }

/* SymbolListAdd() - add new symbol to a list (duh)
 *
 * Note that it is OK to pass in a NULL pointer for the symbol
 * that is being added. We use NULL pointers as placeholders for
 * operands in the symbol lists that describe operators.
 */
#undef SymbolListAdd
SYMBOLS SymbolListAdd(SYMBOLS Handle, TSymbol* Symbol)
    {
    TList*      List;

    if(Handle == NULL)
        Handle  = SymbolListCreate();

    List    = (TList*)Handle;
    ++List->NSymbols;
    List->Symbols   = realloc(List->Symbols, sizeof(TSymbol*) * List->NSymbols);
    assert(List->Symbols != NULL);
    List->Symbols[List->NSymbols-1] = Symbol;

    return Handle;
    }


